// 两两交换
public class SwapPairs {

  /**
   * 第一种方法：画图法
   * 定义一个虚拟头节点，cur指向虚拟头节点，cur后面两个节点进行交换
   * 注意：在改变指针的时候，需要将两个指针进行保留：
   * 交换两个节点的第一个节点和两个节点后一个节点，防止指针丢失
   * 交换后，需要将cur向后移动两位
   * 
   * 时间复杂度：O(n)
   * 空间复杂度：O(1)
   */
  public ListNode swapPairs(ListNode head) {
    ListNode dummyhead = new ListNode(0);
    dummyhead.next = head;
    ListNode cur = dummyhead;
    while (cur.next != null && cur.next.next != null) {
      ListNode temp1 = cur.next;
      ListNode temp2 = cur.next.next.next;
      cur.next = cur.next.next;
      cur.next.next = temp1;
      temp1.next = temp2;
      cur = cur.next.next;
    }

    return dummyhead.next;
  }

  // 定义一个指针的节点
  class ListNode {
    // 节点的值
    int val;
    // 下一个节点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {

    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
      this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}
